from typing import *


class Solution:

    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        d = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1),
             (1, -2)]
        x = y = 0
        n = len(grid)

        def f(p):
            return p >= 0 and p < n

        for i in range(n * n):
            if grid[x][y] != i:
                return False
            for nx, ny in d:
                if f(nx + x) and f(ny + y) and grid[nx + x][ny + y] == i + 1:
                    x, y = nx + x, ny + y
                    break
        return True


s = Solution()
print(
    s.checkValidGrid([[0, 11, 16, 5, 20], [17, 4, 19, 10,
                                           15], [12, 1, 8, 21, 6],
                      [3, 18, 23, 14, 9], [24, 13, 2, 7, 22]]))

s = "12345"
from itertools import pairwise

for x, y in pairwise(s):
    print(x, y)


class Solution:

    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        pos = [0] * (len(grid)**2)
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                pos[x] = (i, j)  # 记录坐标
        if pos[0] != (0, 0):  # 必须从左上角出发
            return False
        for (i, j), (x, y) in pairwise(pos):
            dx, dy = abs(x - i), abs(y - j)  # 移动距离
            if (dx != 2 or dy != 1) and (dx != 1 or dy != 2):  # 不合法
                return False
        return True
